package com.atwy.graph.uf;

/**
 * @Author: 小王子火
 * @Date: 2023/2/8
 * 并查集的完整代码实现（优化思路来自labuladong大神 https://mp.weixin.qq.com/s/gUwLfi25TYamq8AJVIopfA）
 * 使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。
 * 怎么用森林来表示连通性呢？我们设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针指向自己。
 *
 * 森林p 和 森林q 的根节点是同一个，则 p 和 q 就是连通的了
 *
 * 那么这个算法的复杂度是多少呢？我们发现，主要 APIconnected和union中的复杂度都是find函数造成的，所以说它们的复杂度和find一样。
 *
 * find主要功能就是从某个节点向上遍历到树根，其时间复杂度就是树的高度。我们可能习惯性地认为树的高度就是logN，但这并不一定。
 * logN的高度只存在于平衡二叉树，对于一般的树可能出现极端不平衡的情况，使得「树」几乎退化成「链表」，树的高度最坏情况下可能变成N。
 *
 * find,union,connected的时间复杂度都是 O(N)。这个复杂度很不理想的，
 * 你想图论解决的都是诸如社交网络这样数据规模巨大的问题，对于union和connected的调用非常频繁，每次调用需要线性时间完全不可忍受。
 *  我们要知道哪种情况下可能出现不平衡现象，关键在于union过程：
 *  我们一开始就是简单粗暴的把p所在的树接到q所在的树的根节点下面，那么这里就可能出现「头重脚轻」的不平衡状况，
 *  长此以往，树可能生长得很不平衡。我们其实是希望，小一些的树接到大一些的树下面，这样就能避免头重脚轻，更平衡一些。
 *  解决方法是额外使用一个size数组，记录每棵树包含的节点数，我们不妨称为「重量」
 */
public class SimpleUF implements UFInterface{
    /** 统计连通分量个数 */
    private int count;
    /** 节点 x 的父节点是 parent[x] */
    private int[] parent;

    /** 初始化 */
    public SimpleUF(int n) {
        count = n;
        // 初始时每个节点的根节点指向自己
        parent = new int[n];
        for (int i=0; i < n; i++){
            parent[i] = i;
        }
    }
    /** 将 p 和 q 连接 */
    @Override
    public void union(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)return;
        // 将两颗树合到一起
        // parent[rootQ] = rootP;也可以
        parent[rootP] = rootQ;
        count--;
    }
    /** 判断 p和q 是否连通*/
    @Override
    public boolean connected(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    /** 返回图中有多少个连通分量 */
    @Override
    public int count(){
        return count;
    }

    /** 返回某个节点 x 的根节点 */
    private int find(int p) {
        // 根节点的父节点是自己
        while (p != parent[p]){
            p = parent[p];
        }
        return p;
    }
}
